template <typename T>
class CTree;


template <typename T>
class CTreeIterator
{
public:
	CTreeIterator(){}

private:
	T* ptr;
};

template <typename T>
class CTreeNode
{
public:
	CTreeNode(T t):data(t),pLChiled(NULL),pRChiled(NULL){}
	bool operator < (CTreeNode& node)
	{
		return this->data < node.data;
	}

	bool operator > (CTreeNode& node)
	{
		return this->data > node.data;
	}

	bool operator == (CTreeNode& node)
	{
		return this->data == node.data;
	}

	int compareData(T t)
	{
		if (data==t)
		{
			return 0;
		}
		else if (data>t)
		{
			return 1;
		}
		else
		{
			return -1;
		}
	}
	
	bool isLeaf()
	{
		return pLChiled==NULL&&pRChiled==NULL;
	}
	bool hasOneChild()
	{
		return (pLChiled==NULL&&pRChiled!=NULL)||(pLChiled!=NULL&&pRChiled==NULL);
	}
	void setData(T t)
	{
		data = t;
	}
private:
	T data;
	CTreeNode* pLChiled;
	CTreeNode* pRChiled;
	template <typename T> friend class CTree;
};


template <typename T>
class CTree
{
public:
	typedef CTreeNode<T>* pTreeNode;
	typedef CTreeNode<T> TreeNode;

	CTree():pRoot(NULL){}
	CTree(T data):pRoot(new TreeNode(data)){}
	~CTree(){
		while(pRoot!=NULL)
		{
			remove(pRoot->data);
		}
	}
	pTreeNode insert(T node);
	void remove(T t);
	pTreeNode search(T t);


private:

	pTreeNode pRoot; 

	pTreeNode _searchParent(T t);
};

template<typename T>
CTreeNode<T>* CTree<T>::insert(T node)
{
	pTreeNode pNode = new TreeNode(node);
	if (pRoot==NULL)
	{
		pRoot = pNode;
		return pRoot;
	}
	pTreeNode pNodeTemp = pRoot;
	do 
	{
		if (*pNode<*pNodeTemp)
		{
			if (pNodeTemp->pLChiled==NULL)
			{
				pNodeTemp->pLChiled = pNode;
				break;
			}
			pNodeTemp = pNodeTemp->pLChiled;
		}else if (*pNode>*pNodeTemp)
		{
			if (pNodeTemp->pRChiled==NULL)
			{
				pNodeTemp->pRChiled = pNode;
				break;
			}
			pNodeTemp = pNodeTemp->pRChiled;
		}
		else
		{
			return pNodeTemp;
		}
	} while (1);
	return pNode;
}

template<typename T>
void CTree<T>::remove(T t)
{
	pTreeNode pNode= search(t);
	pTreeNode pParentNode = _searchParent(t);
	if (pNode==NULL)
	{
		return;
	}
	if (pNode->isLeaf())
	{
		if (pParentNode==NULL)
		{
			delete pNode;
			pRoot = NULL;
			return;
		}
		if (pParentNode->pLChiled==pNode)
		{
			delete pNode;
			pParentNode->pLChiled = NULL;
		}else
		{
			delete pNode;
			pParentNode->pRChiled = NULL;
		}
	}else if (pNode->hasOneChild())
	{
		if (pParentNode==NULL)
		{
			if (pNode->pLChiled!=NULL)
			{
				pRoot = pNode->pLChiled;
			}
			else
			{
				pRoot = pNode->pRChiled;
			}
			delete pNode;
			return;
		}

		if (pParentNode->pLChiled==pNode)
		{
			if (pNode->pLChiled!=NULL)
			{
				pParentNode->pLChiled = pNode->pLChiled;
			}
			else
			{
				pParentNode->pLChiled = pNode->pRChiled;
			}
			delete pNode;

		}else
		{
			if (pNode->pRChiled!=NULL)
			{
				pParentNode->pRChiled = pNode->pLChiled;
			}
			else
			{
				pParentNode->pRChiled = pNode->pRChiled;
			}
			delete pNode;
		}
	}else
	{
		pTreeNode pTempNode = pNode->pLChiled;
		pTreeNode pTempParentNode = pNode;
		while(pTempNode->pRChiled!=NULL)
		{
			pTempParentNode = pTempNode;
			pTempNode = pTempNode->pRChiled;
		}
		pNode->setData(pTempNode->data);
		if (pTempParentNode==pNode)
		{
			pTempParentNode->pLChiled = pTempNode->pLChiled;
			delete pTempNode;

		}
		else
		{
			pTempParentNode->pRChiled = pTempNode->pLChiled;
			delete pTempNode;
		}
	}
}

template <typename T>
CTreeNode<T>* CTree<T>::search(T t)
{
	pTreeNode pNode = pRoot;
	while(pNode!=NULL)
	{
		if (pNode->compareData(t)==0)
		{
			return pNode;
		}else if (pNode->compareData(t)<0)
		{
			pNode = pNode->pRChiled;
			continue;
		}else
		{
			pNode = pNode->pLChiled;
			continue;
		}

	}
	return NULL;
}

template <typename T>
CTreeNode<T>* CTree<T>::_searchParent(T t)
{
	pTreeNode pNode = pRoot;
	pTreeNode pParentNode = NULL;
	while(pNode!=NULL)
	{
		if (pNode->compareData(t)==0)
		{
			return pParentNode;
		}else if (pNode->compareData(t)<0)
		{
			pParentNode = pNode;
			pNode = pNode->pRChiled;
			continue;
		}else
		{
			pParentNode = pNode;
			pNode = pNode->pLChiled;
			continue;
		}
	}
	return NULL;
}